import java.util.Scanner;

/**
 * Created With IntelliJ IDEA
 * Description:牛客网: 首页 > 试题广场 > 斐波那契凤尾
 * <a href="https://www.nowcoder.com/questionTerminal/c0a4b917a15f40a49ca10532ab9019fb">...</a>
 * User: DELL
 * Data: 2023-04-25
 * Time: 13:33
 */
public class Main {
    /**
     * 本题有两个注意事项 (一直跑不过就是因为这两个)
     * 1. 因为本题是多组输入,且题目中设定的输入组数很多,因此我们需要那空间换取时间,
     * 因为 n <= 100000,因此我们需要事先初始化好 斐波那契数组,之后对应输出即可,
     * 而如果我们每次根据一个输入进行两个变量的动态规划法跑,就会导致超时.(如果是一次输入,
     * 或者是组数较少的时候,使用动态规划法肯定是最好的选择,时间和空间性能都会很好)
     * 2. 本题有一个非常隐晦的坑,就是当要求的斐波那契数大于 6 位的时候,我们要输出
     * 这个数的后六位,我们能想到的第一想法肯定是对 1000_000 去余,但是这样子就可能
     * 会导致取余后的数的前导 0 消失,导致输出不足六位,因此我们需要用 printf 中的
     * %06d 的输出格式来进行约束.
     * @param args
     */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] temp = new int[100001];
        temp[0] = 1;
        temp[1] = 1;
        for (int i = 2; i < 100001; i++) {
            temp[i] = (temp[i-2] + temp[i-1]) % 1000000;
        }
        //第 26 个斐波那契数为第一个 6 位数
        int flag = 26;
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            if (n < flag) {
                System.out.println(temp[n]);
            } else {
                System.out.printf("%06d\n", temp[n]);
            }
        }
    }
}
